#!/usr/bin/env python
#-*- coding: utf-8 -*-

from KemenyYoung import S


## Schulze method helper: Generates all possible paths
#  @param   cs  A list of all possible candidates (e.g. any voter’s preference ordering)
#  @param   d   A dict: For candidates c1, c2, gives the number of pairwise comparisons won by c2 as d[(c1, c2)]
#  @returns A list of all possible paths according to the Schulze method
def paths(cs, d, currentpath=[], allpaths=[]):
    if len(currentpath) == len(cs):
        allpaths.append(currentpath)
    elif not currentpath:
        for c in cs:
            paths(cs, d, [c], allpaths)
    else:
        allpaths.append(currentpath)
        for c in cs:
            if c not in currentpath and d[(currentpath[-1], c)] > d[(c, currentpath[-1])]:
                paths(cs, d, currentpath+[c], allpaths)

                
## Schulze method helper: Strength p of a path
#  @param   path    The path
#  @param   d   A dict: For candidates c1, c2, gives the number of pairwise comparisons won by c2 as d[(c1, c2)]
#  @returns The strength of the path (=minimum of the d values)
def path_strength(path, d):
    m = -1
    for i in range(len(path)-1):
        if m == -1 or m > d[(path[i], path[i+1])]:
            m = d[(path[i], path[i+1])]
    return m if m > -1 else 0


## Implements the Schulze election method
#  @param   P   A list of preference orderings (one per voter)
#  @returns The winning alternative (=candidate)
def Schulze(P):
    ## calculate the d(x,y) measure
    d = {}
    for c1 in P[0]:
        for c2 in P[0]:
            if c1 != c2:
                d[(c1, c2)] = S(c1, c2, P)

    ## generate the paths
    allpaths = []
    paths(P[0], d, [], allpaths)

    ## calculate the p(·,·) function (maximum path strength)
    p = {}
    for path in allpaths:
        if len(path) >= 2 and ((path[0], path[-1]) not in p.keys() or p[(path[0], path[-1])] < path_strength(path, d)):
            p[(path[0], path[-1])] = path_strength(path, d)

    ## fill missing entries
    for c in P[0]:
        for c2 in [i for i in P[0] if i!=c]:
            if (c, c2) not in p.keys():
                p[(c, c2)] = 0

    ## prettyprint p(·,·)
    print ""
    print " p   |",
    for x in sorted(P[0]):
        print "%3s |" % x,
    print ""
    print "".join(["-----+" for i in range(len(P[0])+1)])
    for y in sorted(P[0]):
        print "%4s |" % y,
        for x in sorted(P[0]):
            if (x, y) in p.keys():
                print "%3s |" % p[(x, y)],
            else:
                print "  \ |",
        print ""
    print ""

    ## find the (possible) winners
    winners = []
    for c in P[0]:
        for c2 in [i for i in P[0] if i!=c]:
            if p[(c2, c)] < p[(c, c2)]:
                break
        else:
            winners.append(c)

    if len(winners) == 1:
        print "Winner:", winners, "\n"
    else:
        print "Possible winners:", winners, "\n"

    

if __name__ == '__main__':

    print ""
    print "(Example 86 from the lecture)"
    ## expected result: possible winners b and d
    P = ['dcba'] * 3 \
      + ['cbad'] * 2 \
      + ['acbd'] * 2 \
      + ['adbc'] * 2
    Schulze(P)

    print ""
    print "(Exercise 9.2)"
    P = ['badec'] * 25 \
      + ['edcba'] * 12 \
      + ['ceabd'] * 11 \
      + ['dabec'] * 14 \
      + ['ebdca'] * 18 \
      + ['cdaeb'] * 10 \
      + ['cdeba'] * 10
    Schulze(P)
